package leetcode.weekly.week332;

//Solution4Test
public class Solution4 {
	public int minimumScore(String s, String t) {
		char[] cs = s.toCharArray();
		char[] ct = t.toCharArray();
		boolean[] d = new boolean[ct.length];
		for (int i = 0, j = 0; i < cs.length && j < ct.length; i++) {
			int s1 = cs[i];
			while (j < d.length && ct[j] != s1) {
				d[j] = true;
				j++;
			}
			if (j < ct.length && ct[j] == s1) {
				j++;
			}
		}
		int del = -1;
		for (int i = ct.length - 1; i >= 0; i--) {
			if (d[i]) {
				del = i;
				break;
			}
		} 
		int not = -1;
		for (int i = del; i >= 0; i--) {
			if (!d[i]) {
				not = i;
				break;
			}
		}
		if (del != -1 && not != -1 && ct[not] == ct[del]) {
			d[not] = true;
			d[del] = false;
		}
		int r = -1;
		for (int i = ct.length - 1; i >= 0; i--) {
			if (d[i]) {
				r = i;
				break;
			}
		}
		int l = -1;
		for (int i = 0; i < ct.length; i++) {
			if (d[i]) {
				l = i;
				break;
			}
		}
		return r - l + 1;
	}

}
